package org.xingole.leetcode.das.monoqueue;

import java.util.Comparator;
import java.util.PriorityQueue;

public class SlidingWindowMaximum {

     public int[] maxSlidingWindow(int[] nums, int k) {
          return null;
     }

     public int[] maxSlidingWindowWithHeap(int[] nums, int k) {
          int n = nums.length;

          // (num, index): the num and the corresponding index in nums array.
          PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {

               @Override
               public int compare(int[] pair1, int[] pair2) {
                    return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
               }
               
          });

          // create the initial window.
          for (int i = 0; i < k; i++) {
               pq.offer(new int[]{nums[i], i});
          }

          int[] ans = new int[n - k + 1];
          ans[0] = pq.peek()[0];
          // move the window
          for ( int i = k; i < n; i++ ) {
               pq.offer(new int[]{nums[i], i});
               // remove the element out of the windows.
               while (pq.peek()[1] <= i - k) {
                    pq.poll();
               }

               ans[i - k + 1] = pq.peek()[0];
          }

          return ans;
     }
}
